package q919_CBTInserter;


import CommonClass.Common.TreeNode;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

/*
用简单的方式来模拟完全二叉树插入器：
用一个prevNodes队列来记录所有父节点，意味着这个队列中剩下的所有节点的左右子节点还没有被插入完全
而curNodes就是接下来被依次插入的节点
cur记录了当前第一个还有空位没有被插入的节点
（需要注意的是 如果curNode的数量恰好是prev的两倍 则代表prev已经被插满了 需要将prev更新）

那么插入节点时 只需要查看当前cur是否有空位 有则插入 并将插入的节点记录到curNodes中
如果没有 则考虑prev中是否还有节点 如果有则弹出节点为新的cur 没有则更新prev

 */
public class CBTInserter1 {

    Deque<TreeNode> prevNodes;
    Deque<TreeNode> curNodes;
    TreeNode cur, root;
    public CBTInserter1(TreeNode root) {
        prevNodes = new LinkedList<>();
        curNodes = new LinkedList<>();
        this.root = root;
        Queue<TreeNode> temp = new LinkedList<>();
        temp.offer(root);
        while (!temp.isEmpty()) {
            int size = temp.size();
            prevNodes.clear();
            curNodes.clear();
            cur = null;
            for (int i = 0; i < size; i++) {
                TreeNode node = temp.poll();
                prevNodes.offer(node);

                if (cur == null && (node.left == null || node.right == null)) cur = node;

                if (node.left != null) {
                    temp.offer(node.left);
                    curNodes.offer(node.left);
                }

                if (node.right != null) {
                    temp.offer(node.right);
                    curNodes.offer(node.right);
                }
            }
            boolean flag = false;
            for (TreeNode curNode : curNodes) {
                if (curNode.left != null || curNode.right != null) flag = true;
            }

            if (!flag) break;
        }

        if (curNodes.size() == prevNodes.size() * 2) {
            prevNodes = new LinkedList<>(curNodes);
            cur = prevNodes.poll();
            curNodes.clear();
        }

    }

    public int insert(int val) {
        if (cur.left == null) {
            cur.left = new TreeNode(val);
            curNodes.offer(cur.left);
            return cur.val;
        } else if (cur.right == null) {
            cur.right = new TreeNode(val);
            curNodes.offer(cur.right);
            return cur.val;
        } else if (prevNodes.isEmpty()) {
            prevNodes = new LinkedList<>(curNodes);
            curNodes.clear();
            cur = prevNodes.poll();
            return insert(val);
        } else {
            cur = prevNodes.poll();
            return insert(val);
        }
    }

    public TreeNode get_root() {
        return root;
    }
}
